{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Rows Covered by Columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #enumeration #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #枚举 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumRows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #被列覆盖的最多行数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0 </strong>开始、大小为 <code>m x n</code> 的二进制矩阵 <code>matrix</code> ；另给你一个整数 <code>numSelect</code>，表示你必须从 <code>matrix</code> 中选择的 <strong>不同</strong> 列的数量。</p>\n",
    "\n",
    "<p>如果一行中所有的 <code>1</code> 都被你选中的列所覆盖，则认为这一行被 <strong>覆盖</strong> 了。</p>\n",
    "\n",
    "<p><strong>形式上</strong>，假设 <code>s = {c<sub>1</sub>, c<sub>2</sub>, ...., c<sub>numSelect</sub>}</code> 是你选择的列的集合。对于矩阵中的某一行 <code>row</code> ，如果满足下述条件，则认为这一行被集合 <code>s</code> <strong>覆盖</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于满足 <code>matrix[row][col] == 1</code> 的每个单元格 <code>matrix[row][col]</code>（<code>0 &lt;= col &lt;= n - 1</code>），<code>col</code> 均存在于 <code>s</code> 中，或者</li>\n",
    "\t<li><code>row</code> 中 <strong>不存在</strong> 值为 <code>1</code> 的单元格。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要从矩阵中选出 <code>numSelect</code> 个列，使集合覆盖的行数最大化。</p>\n",
    "\n",
    "<p>返回一个整数，表示可以由 <code>numSelect</code> 列构成的集合 <strong>覆盖</strong> 的 <strong>最大行数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/14/rowscovered.png\" style=\"width: 250px; height: 417px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "图示中显示了一种覆盖 3 行的可行办法。\n",
    "选择 s = {0, 2} 。\n",
    "- 第 0 行被覆盖，因为其中没有出现 1 。\n",
    "- 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。\n",
    "- 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。\n",
    "- 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。\n",
    "因此，可以覆盖 3 行。\n",
    "另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/14/rowscovered2.png\" style=\"width: 83px; height: 247px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1],[0]], numSelect = 1\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。\n",
    "所以我们返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 12</code></li>\n",
    "\t<li><code>matrix[i][j]</code> 要么是 <code>0</code> 要么是 <code>1</code></li>\n",
    "\t<li><code>1 &lt;= numSelect&nbsp;&lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-rows-covered-by-columns](https://leetcode.cn/problems/maximum-rows-covered-by-columns/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-rows-covered-by-columns](https://leetcode.cn/problems/maximum-rows-covered-by-columns/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0],[1,0,1],[0,1,1],[0,0,1]]\\n2', '[[1],[0]]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dd = {i:set([j for j in range(n) if mat[i][j]!=0]) for i in range(m)}\n",
    "        choices = list(map(set,combinations(range(n),cols)))\n",
    "        res = 0\n",
    "        # print(dd, choices)\n",
    "        for choice in choices:\n",
    "            # print('1',choice)\n",
    "            tmp = 0\n",
    "            for v in dd.values():\n",
    "                # print(v,choice,v.issubset(choice))\n",
    "                if v.issubset(choice):\n",
    "                    tmp += 1\n",
    "            res = max(tmp, res)\n",
    "            if res==m: return res\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], cols: int) -> int:\n",
    "        res = 0\n",
    "        m = [sum(v << j for j, v in enumerate(r)) for r in matrix]\n",
    "        for set in range(1 << len(matrix[0])):\n",
    "            if set.bit_count() == cols:\n",
    "                res = max(res, sum(row & set == row for row in m))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rows = [0] * m\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, c in enumerate(row):\n",
    "                rows[i] += c << j\n",
    "        ans = 0\n",
    "        for k in range(1 << n):\n",
    "            if bin(k).count('1') == numSelect:\n",
    "                ans = max(ans, sum(row & k == row for row in rows))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        can = list(combinations(range(n), cols))\n",
    "        s = []\n",
    "        for c in can:\n",
    "            s.append(set(c))\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            t = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] == 1:\n",
    "                        if j not in c:\n",
    "                            break\n",
    "                else:\n",
    "                    t += 1\n",
    "            ans = max(ans, t)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        for set in range(1 << len(mat[0])):\n",
    "            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求\n",
    "                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        can = list(combinations(range(n), cols))\n",
    "        s = []\n",
    "        for c in can:\n",
    "            s.append(set(c))\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            t = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] == 1:\n",
    "                        if j not in c:\n",
    "                            break\n",
    "                else:\n",
    "                    t += 1\n",
    "            ans = max(ans, t)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(matrix)]\n",
    "        set = (1<<numSelect) -1\n",
    "        r = 1 << n\n",
    "        while set < r:\n",
    "            ans = max(ans, sum(row&set == row for row in mask))\n",
    "            lb = set&-set\n",
    "            x = set + lb\n",
    "            set = (set^x)//lb>>2 | x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        A = [set(j for j in range(n) if matrix[i][j]) for i in range(m)]\n",
    "        return max(sum(not s0 - s1 for s0 in A) for s1 in map(set, combinations(range(n), numSelect)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        for set in range(1 << len(mat[0])):\n",
    "            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求\n",
    "                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        path = []\n",
    "        n = len(matrix[0])\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if len(path) == numSelect:\n",
    "                allCoverLines = 0\n",
    "                print(path)\n",
    "                for i in range(len(matrix)):\n",
    "                    allCover = True\n",
    "                    for j in range(n):\n",
    "                        if matrix[i][j] == 1 and j not in path:\n",
    "                            allCover = False\n",
    "                            break\n",
    "                    if allCover:\n",
    "                        allCoverLines += 1\n",
    "                ans = max(ans, allCoverLines)\n",
    "                return\n",
    "            if i == n:\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                path.append(j)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools as it\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        nCol = len(matrix[0])\n",
    "        iterC = it.combinations(range(nCol), numSelect)\n",
    "        rtnMax = 0\n",
    "        for eachS in iterC:\n",
    "            coverNum = 0\n",
    "            for eachRow in matrix:\n",
    "                if all(map(lambda idx: False if eachRow[idx] and (idx not in eachS) else True, range(nCol))):\n",
    "                    coverNum += 1\n",
    "            rtnMax = max(rtnMax, coverNum)\n",
    "        return rtnMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        ans=0\n",
    "        mask=[sum(v<<j for j,v in enumerate(row)) for i,row in enumerate(matrix)]\n",
    "        print(mask)\n",
    "        set_=(1<<numSelect)-1\n",
    "        while set_<1<<m:\n",
    "            ans=max(ans,sum(row&set_ ==row for row in mask))\n",
    "            lb=set_&-set_\n",
    "            x=set_+lb\n",
    "            set_=(set_^x)//lb>>2 | x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        sm = [sum(i) for i in matrix]\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        ans = 0\n",
    "        path = []\n",
    "        def f(i,remain):\n",
    "            if remain == 0:\n",
    "                t = 0\n",
    "                for j in range(m):\n",
    "                    if sm[j]==sum([matrix[j][k] for k in path]):\n",
    "                        t += 1\n",
    "                nonlocal ans\n",
    "                ans = max(ans, t)\n",
    "                return\n",
    "            elif i == n:\n",
    "                return\n",
    "            f(i+1,remain)\n",
    "\n",
    "            path.append(i)\n",
    "            f(i+1,remain-1)\n",
    "            path.pop()\n",
    "        f(0,numSelect)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        for set in range(1 << len(mat[0])):\n",
    "            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求\n",
    "                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        \n",
    "        \n",
    "        mask=[sum(v<<j for j,v in enumerate(row)) for row in matrix]\n",
    "        ret=0\n",
    "        for st in range(1<<len(matrix[0])):\n",
    "            if st.bit_count()!=numSelect:\n",
    "                continue\n",
    "            cnt=0\n",
    "            for row in mask:\n",
    "                if row&st==row:\n",
    "                    cnt+=1\n",
    "            ret=max(ret,cnt)\n",
    "        return ret\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count_ones_in_binary(self, num):\n",
    "        # 将整数转换为二进制字符串并去掉前缀'0b'\n",
    "        binary_str = bin(num)[2:]\n",
    "        # 使用字符串的count方法来计算'1'的出现次数\n",
    "        count = binary_str.count('1')\n",
    "        return count\n",
    "\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        # just a simple binary enumerate\n",
    "        binary_value_of_rows = []\n",
    "        for row in matrix:\n",
    "            binary_value = 0\n",
    "            # 去除前导零\n",
    "            first_non_zero = 0\n",
    "            while first_non_zero < len(row) and row[first_non_zero] == 0:\n",
    "                first_non_zero += 1\n",
    "            row = row[first_non_zero:]\n",
    "            for element in row:\n",
    "                binary_value = (binary_value << 1) + element\n",
    "            binary_value_of_rows.append(binary_value)\n",
    "\n",
    "        # 遍历每种列的选法，然后看其覆盖了多少行。即可\n",
    "        # 遍历各种列的选法，就通过递增 (0 ~ binary_value(all_1))来判断\n",
    "        ans = 0\n",
    "        for i in range(1<<len(matrix[0])):\n",
    "            if self.count_ones_in_binary(i) == numSelect: # i对应的数字 是一种 列的选法\n",
    "                hit_rows = 0\n",
    "                for bv in binary_value_of_rows:\n",
    "                   if bv & i == bv:  # bv二进制是 选择数i的子集\n",
    "                        hit_rows += 1\n",
    "                ans = max(hit_rows, ans)\n",
    "\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/maximum-rows-covered-by-columns/solutions/1798794/by-endlesscheng-dvxe/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        def is_sub(n1,n2):\n",
    "            #n1 是否是 n2 的子集\n",
    "            while n1>0 or n2>0:\n",
    "                if n2&1==1:\n",
    "                    if n1&1==0:\n",
    "                        return False\n",
    "                n1 = n1>>1\n",
    "                n2 = n2>>1\n",
    "            return True\n",
    "        mask = []\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        for row in matrix:\n",
    "            tmp = 0\n",
    "            for j,num in enumerate((row)):\n",
    "                tmp|=(num<<(m-1-j))\n",
    "            mask.append(tmp)\n",
    "        # print(mask)\n",
    "        ans = 0\n",
    "        for i in range(1<<m):\n",
    "            \n",
    "            if i.bit_count()==numSelect:\n",
    "                # print(i)\n",
    "                num = 0\n",
    "                for r in mask:\n",
    "                    if is_sub(i, r):\n",
    "                        num+=1\n",
    "                # print(num)\n",
    "                ans = max(ans, num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        for set in range(1 << len(mat[0])):\n",
    "            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求\n",
    "                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        a=[[] for _ in range(n)]\n",
    "        b=[0]*m\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j]==1:\n",
    "                    a[j].append(i)\n",
    "                    b[i]+=1\n",
    "        ret=0\n",
    "        colsSelect=0\n",
    "        def dfs(i):\n",
    "            nonlocal colsSelect,ret\n",
    "            if i==n or colsSelect==numSelect:\n",
    "                ret=max(ret,b.count(0))\n",
    "                return\n",
    "            rows=a[i]\n",
    "            for j in rows:\n",
    "                b[j]-=1\n",
    "            colsSelect+=1\n",
    "            dfs(i+1)\n",
    "            for j in rows:\n",
    "                b[j]+=1\n",
    "            colsSelect-=1\n",
    "            dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    maxRow = 0\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        n = len(matrix[0])\n",
    "        self.maxRows(matrix,numSelect,n,0)\n",
    "        return self.maxRow\n",
    "    def maxRows(self, matrix:List[List[int]], numSelect:int, n:int, start:int):\n",
    "        if numSelect == 0:\n",
    "            count = 0\n",
    "            for j in range(len(matrix)):\n",
    "                if self.isZeroRow(matrix[j]):\n",
    "                    count +=1\n",
    "                    self.maxRow = max(self.maxRow,count)\n",
    "            return\n",
    "        for i in range(start,n):\n",
    "            l = []\n",
    "            for j in range(len(matrix)):\n",
    "                l.append(matrix[j][i])\n",
    "                matrix[j][i] = 0\n",
    "            numSelect -=1\n",
    "            self.maxRows(matrix,numSelect,n,i+1)\n",
    "            for j in range(len(matrix)):\n",
    "                matrix[j][i] = l[j]\n",
    "            numSelect +=1\n",
    "        \n",
    "    def isZeroRow(self,row:List[int]):\n",
    "        for i in range(len(row)):\n",
    "            if row[i] == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        path = [False] * n\n",
    "\n",
    "        def f():\n",
    "            com = 0\n",
    "            for i in range(m):\n",
    "                signal = True\n",
    "                for j in range(n):\n",
    "                    if path[j]:continue\n",
    "                    if matrix[i][j]==1:\n",
    "                        signal = False\n",
    "                        break\n",
    "                if signal:com+=1\n",
    "            return com\n",
    "\n",
    "        def dfs(i,k):   #目前在第i列，已选择k列\n",
    "            nonlocal ans\n",
    "            if i==n:\n",
    "                if k==numSelect:\n",
    "                    ans = max(ans,f())\n",
    "                return\n",
    "            #不选\n",
    "            dfs(i+1,k)\n",
    "            #选\n",
    "            path[i] = True\n",
    "            dfs(i+1,k+1)\n",
    "            path[i] = False\n",
    "\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        matrixMasks = [reduce(or_,(1<<c for c, v in enumerate(row) if v), 0)\n",
    "                       for row in matrix\n",
    "                       ]\n",
    "        result = 0\n",
    "        for mask in range(1, 1<<n):\n",
    "            if mask.bit_count() != numSelect: continue\n",
    "            covered = sum(1 for m in matrixMasks if m & mask == m)\n",
    "            result = max(result, covered)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        a=[[] for _ in range(n)]\n",
    "        b=[0]*m\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j]==1:\n",
    "                    a[j].append(i)\n",
    "                    b[i]+=1\n",
    "        ret=0\n",
    "        colsSelect=0\n",
    "        def dfs(i):\n",
    "            nonlocal colsSelect,ret\n",
    "            if i==n or colsSelect==numSelect:\n",
    "                ret=max(ret,b.count(0))\n",
    "                return\n",
    "            rows=a[i]\n",
    "            for j in rows:\n",
    "                b[j]-=1\n",
    "            colsSelect+=1\n",
    "            dfs(i+1)\n",
    "            for j in rows:\n",
    "                b[j]+=1\n",
    "            colsSelect-=1\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        path = [0] * len(matrix[0])\n",
    "\n",
    "        def dfs(i, c):\n",
    "            nonlocal ans, numSelect\n",
    "\n",
    "            if i == len(matrix[0]):\n",
    "                if c != numSelect: return\n",
    "                cover = 0\n",
    "                for j in range(len(matrix)):\n",
    "                    flag = 1\n",
    "                    for k in range(len(matrix[j])):\n",
    "                        if matrix[j][k] == 1 and path[k] == 0:\n",
    "                            flag = 0\n",
    "                            break\n",
    "                    cover += flag\n",
    "                ans = max(ans, cover)\n",
    "                return\n",
    "                \n",
    "            dfs(i+1, c)\n",
    "            path[i] = 1\n",
    "            dfs(i+1, c+1)\n",
    "            path[i] = 0\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        k = numSelect\n",
    "        col = [False] * n\n",
    "        ans = 0\n",
    "        def dfs(i: int, cnt: int) -> None:\n",
    "            last = k - cnt\n",
    "            if last > n - i:\n",
    "                return\n",
    "            if cnt == k:\n",
    "                res = 0\n",
    "                for x in range(m):\n",
    "                    ok = True\n",
    "                    for y in range(n):\n",
    "                        if matrix[x][y] and not col[y]:\n",
    "                            ok = False\n",
    "                            break\n",
    "                    if ok:\n",
    "                        res += 1\n",
    "                nonlocal ans\n",
    "                ans = max(ans, res)\n",
    "                return\n",
    "            dfs(i + 1, cnt)\n",
    "            col[i] = True\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            col[i] = False\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m = len(matrix) #行\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        path = []\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return m\n",
    "\n",
    "        def dfs(i):# 表示考虑第k列，目前有s次选择机会\n",
    "            nonlocal matrix,res\n",
    "            if i == n:  # 递归出口\n",
    "                final_path = path[:]\n",
    "                rows = 0   # 被覆盖的行数：sum(matrix[i]) == 该行中，所有被选择列的元素和\n",
    "                if len(final_path) == numSelect:  # 判断选择的列数是否满足要求\n",
    "                    for i in range(m):\n",
    "                        s = 0  # 计算每一行中被选中列的和\n",
    "                        for j in final_path:\n",
    "                            s += matrix[i][j]  \n",
    "                        if sum(matrix[i]) == s:  # 判断 行的和 == 被选中的列在该行中的和 \n",
    "                            rows += 1\n",
    "                    res = max(res, rows)  # 所有行计算完成后，更新res\n",
    "                return\n",
    "            dfs(i + 1)  # 不选i行\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        col = len(matrix[0])\n",
    "        def f(nums):\n",
    "            s = 0\n",
    "            for n in nums:\n",
    "                s = s*2 + n\n",
    "            return s\n",
    "\n",
    "\n",
    "        matrix = [f(m) for m in matrix]\n",
    "        def f(j, n):\n",
    "            if j == col or n == 0:\n",
    "                return matrix.count(0)\n",
    "            s = f(j+1, n)\n",
    "            a = [0]*len(matrix)\n",
    "            for i in range(len(matrix)):\n",
    "                a[i] = matrix[i]\n",
    "                tmp = matrix[i] >> j\n",
    "                if tmp & 1:\n",
    "                    matrix[i] = matrix[i] - 2**j\n",
    "            s = max(s, f(j+1, n-1))\n",
    "            for i in range(len(matrix)):\n",
    "                matrix[i] = a[i]\n",
    "            return s\n",
    "        return f(0, numSelect)\n",
    "                    \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        def isCover(row, path):\n",
    "            for r, c in zip(row, path):\n",
    "                if r==1 and c==0:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        def maxCover(path):\n",
    "            ans = 0\n",
    "            for row in matrix:\n",
    "                ans += isCover(row, path)\n",
    "            return ans\n",
    "        \n",
    "        # 方法一：从答案的角度\n",
    "        # def dfs(i, numSelect):\n",
    "        #     if numSelect==0:\n",
    "        #         m = maxCover(path)\n",
    "        #         nonlocal res\n",
    "        #         res = max(res, m)\n",
    "        #         return\n",
    "\n",
    "        #     for j in range(i, cols):\n",
    "        #         path[j] = 1\n",
    "        #         dfs(j+1, numSelect-1)\n",
    "        #         path[j] = 0\n",
    "        \n",
    "        # cols = len(matrix[0])  \n",
    "        # path = [0] * cols\n",
    "        # res = 0\n",
    "        # dfs(0, numSelect)\n",
    "        # return res\n",
    "        # 方法二：从输入的角度\n",
    "        def dfs(i):\n",
    "            if sum(path)==numSelect:\n",
    "                m = maxCover(path)\n",
    "                nonlocal res\n",
    "                res = max(res, m)\n",
    "                return\n",
    "            if i == cols:\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "            # 选\n",
    "            path[i] = 1\n",
    "            dfs(i+1)\n",
    "            path[i] = 0\n",
    "\n",
    "\n",
    "        cols = len(matrix[0])  \n",
    "        path = [0] * cols\n",
    "        res = 0\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        path = []\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i: int, numSelect: int) -> None:\n",
    "            nonlocal ans\n",
    "            if i == n or numSelect == 0:\n",
    "                cur = 0\n",
    "                for i in range(m):\n",
    "                    is_cover = True\n",
    "                    for j in range(n):\n",
    "                        if matrix[i][j] == 1 and j not in path:\n",
    "                            is_cover = False\n",
    "                            break\n",
    "                    if is_cover:\n",
    "                        cur += 1\n",
    "                ans = max(ans, cur)\n",
    "                return\n",
    "\n",
    "            dfs(i + 1, numSelect)\n",
    "\n",
    "            path.append(i)\n",
    "            dfs(i + 1, numSelect - 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0, numSelect)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        a=[[] for _ in range(n)]\n",
    "        b=[0]*m\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j]==1:\n",
    "                    a[j].append(i)\n",
    "                    b[i]+=1\n",
    "        ret=0\n",
    "        colsSelect=0\n",
    "        def dfs(i):\n",
    "            nonlocal colsSelect,ret\n",
    "            if i==n or colsSelect==numSelect:\n",
    "                ret=max(ret,b.count(0))\n",
    "                return\n",
    "            rows=a[i]\n",
    "            for j in rows:\n",
    "                b[j]-=1\n",
    "            colsSelect+=1\n",
    "            dfs(i+1)\n",
    "            for j in rows:\n",
    "                b[j]+=1\n",
    "            colsSelect-=1\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        for set in range(1 << len(mat[0])):\n",
    "            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求\n",
    "                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], col: int) -> int:\n",
    "        rows = []\n",
    "        for row in mat:\n",
    "            sum = 0\n",
    "            for j, v in enumerate(row):\n",
    "                sum += v << j\n",
    "            rows.append(sum)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1 << len(mat[0])):\n",
    "            if i.bit_count() != col:\n",
    "                continue\n",
    "            cnt = 0\n",
    "            for row in rows:\n",
    "                if row & i == row:\n",
    "                    cnt += 1\n",
    "            res = max(res, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        path = []\n",
    "        res = 0\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i == n:\n",
    "                final_path = path.copy()\n",
    "                if len(final_path) == numSelect:\n",
    "                    rows = 0\n",
    "                    for j in range(m):\n",
    "                        s = 0\n",
    "                        for k in final_path:\n",
    "                            s += matrix[j][k]\n",
    "                        if sum(matrix[j]) == s:\n",
    "                            rows+=1\n",
    "                    res = max(res, rows)\n",
    "                return\n",
    "            \n",
    "            dfs(i+1)\n",
    "\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        # 1. 选/不选\n",
    "        m = len(matrix)   # 行数\n",
    "        n = len(matrix[0])  # 列数\n",
    "        path = []  # 用来存放被选择的列的编号\n",
    "        res = 0  # 被覆盖的行数\n",
    "\n",
    "        def dfs(i):\n",
    "            # 所有的列都有选和不选的情况，但是只有选择列的数量len(path) == numSelect时，才会进一步计算覆盖的行数，继而更新res的最大值\n",
    "            nonlocal res\n",
    "\n",
    "            if i == n:  # 递归出口\n",
    "                final_path = path[:]\n",
    "                rows = 0   # 被覆盖的行数：sum(matrix[i]) == 该行中，所有被选择列的元素和\n",
    "                if len(final_path) == numSelect:  # 判断选择的列数是否满足要求\n",
    "                    for i in range(m):\n",
    "                        s = 0  # 计算每一行中被选中列的和\n",
    "                        for j in final_path:\n",
    "                            s += matrix[i][j]  \n",
    "                        if sum(matrix[i]) == s:  # 判断 行的和 == 被选中的列在该行中的和 \n",
    "                            rows += 1\n",
    "                    res = max(res, rows)  # 所有行计算完成后，更新res\n",
    "                return\n",
    "            \n",
    "            dfs(i + 1)  # 不选i行\n",
    "\n",
    "            path.append(i)  # 选择i行，将i加入path中\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m = len(matrix)   # 行数\n",
    "        n = len(matrix[0])  # 列数\n",
    "        #m是行，n是列\n",
    "        ans = 0\n",
    "        def dfs(index,attr):\n",
    "            if len(attr) == numSelect:\n",
    "                tempans = 0\n",
    "                for item in matrix:\n",
    "                    if sum(item) == sum([subitem for idx,subitem, in enumerate(item) if idx in  attr ]):\n",
    "                        tempans+=1\n",
    "                nonlocal ans\n",
    "                ans = max(ans,tempans)\n",
    "                #判断路径\n",
    "                return \n",
    "            for i in range(index,n):\n",
    "                \n",
    "                dfs(i+1,attr+[i])\n",
    "            \n",
    "        dfs(0,[])\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for row in matrix]\n",
    "        ans = 0\n",
    "        for set in range(1 << len(matrix[0])):\n",
    "            if set.bit_count() != numSelect:\n",
    "                continue\n",
    "            cnt = 0\n",
    "            for row in mask:\n",
    "                cnt += (row & set) == row\n",
    "            ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        k = numSelect\n",
    "        col = [False] * n\n",
    "        ans = 0\n",
    "        def dfs(i: int, cnt: int) -> None:\n",
    "            last = k - cnt\n",
    "            if last > n - i:\n",
    "                return\n",
    "            if cnt == k:\n",
    "                res = 0\n",
    "                for x in range(m):\n",
    "                    ok = True\n",
    "                    for y in range(n):\n",
    "                        if matrix[x][y] and not col[y]:\n",
    "                            ok = False\n",
    "                            break\n",
    "                    if ok:\n",
    "                        res += 1\n",
    "                nonlocal ans\n",
    "                ans = max(ans, res)\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                col[j] = True\n",
    "                dfs(j + 1, cnt + 1)\n",
    "                col[j] = False\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        idxCounter = collections.Counter()\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        def dfs(i, cnt=0):\n",
    "            if len(idxCounter) > numSelect:\n",
    "                return\n",
    "            if i == len(matrix):\n",
    "                nonlocal ans\n",
    "                ans = max(ans, cnt)\n",
    "                return\n",
    "            dfs(i+1, cnt)\n",
    "            for idx,m in enumerate(matrix[i]):\n",
    "                if m:\n",
    "                    idxCounter[idx] += 1\n",
    "            dfs(i+1, cnt+1)\n",
    "            for idx,m in enumerate(matrix[i]):\n",
    "                if m:\n",
    "                    idxCounter[idx] -= 1\n",
    "                    if idxCounter[idx] == 0:\n",
    "                        del idxCounter[idx]\n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, mat: List[List[int]], cols: int) -> int:\n",
    "        ans = 0\n",
    "        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]\n",
    "        set = (1 << cols) - 1\n",
    "        while set < 1 << len(mat[0]):\n",
    "            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖\n",
    "            lb = set & -set\n",
    "            x = set + lb\n",
    "            set = (set ^ x) // lb >> 2 | x\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "\n",
    "        # 1. 选/不选\n",
    "        m = len(matrix)   # 行数\n",
    "        n = len(matrix[0])  # 列数\n",
    "        path = []  # 用来存放被选择的列的编号\n",
    "        res = 0  # 被覆盖的行数\n",
    "\n",
    "        def dfs(i):\n",
    "            # 所有的列都有选和不选的情况，但是只有选择列的数量len(path) == numSelect时，才会进一步计算覆盖的行数，继而更新res的最大值\n",
    "            nonlocal res\n",
    "\n",
    "            if i == n:  # 递归出口\n",
    "                final_path = path[:]\n",
    "                rows = 0   # 被覆盖的行数：sum(matrix[i]) == 该行中，所有被选择列的元素和\n",
    "                if len(final_path) == numSelect:  # 判断选择的列数是否满足要求\n",
    "                    for i in range(m):\n",
    "                        s = 0  # 计算每一行中被选中列的和\n",
    "                        for j in final_path:\n",
    "                            s += matrix[i][j]  \n",
    "                        if sum(matrix[i]) == s:  # 判断 行的和 == 被选中的列在该行中的和 \n",
    "                            rows += 1\n",
    "                    res = max(res, rows)  # 所有行计算完成后，更新res\n",
    "                return\n",
    "            \n",
    "            dfs(i + 1)  # 不选i行\n",
    "\n",
    "            path.append(i)  # 选择i行，将i加入path中\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        # m = len(matrix)\n",
    "        # n = len(matrix[0])\n",
    "        # path = []\n",
    "        # ans = 0\n",
    "        # def dfs(i):\n",
    "        #     nonlocal ans\n",
    "        #     if i == n:\n",
    "        #         rows = 0\n",
    "        #         if len(path.copy()) == numSelect:\n",
    "        #             for i in range(m):\n",
    "        #                 s = 0\n",
    "        #                 for j in path.copy():\n",
    "        #                     s += matrix[i][j]\n",
    "        #                 if s == sum(matrix[i]):\n",
    "        #                     rows += 1\n",
    "        #             ans = max(ans,rows)\n",
    "        #         return\n",
    "        #     dfs(i+1)\n",
    "\n",
    "        #     path.append(i)\n",
    "        #     dfs(i+1)\n",
    "        #     path.pop()\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        path = []\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            rows = 0\n",
    "            if len(path.copy()) == numSelect:\n",
    "                for i in range(m):\n",
    "                    s = 0\n",
    "                    for j in path.copy():\n",
    "                        s += matrix[i][j]\n",
    "                    if s == sum(matrix[i]):\n",
    "                        rows += 1\n",
    "                ans = max(ans,rows)\n",
    "                return\n",
    "            if i == n:\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                path.append(j)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        idxCounter = collections.Counter()\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        def dfs(i, cnt=0):\n",
    "            if len(idxCounter) > numSelect:\n",
    "                return\n",
    "            if i == len(matrix):\n",
    "                nonlocal ans\n",
    "                ans = max(ans, cnt)\n",
    "                return\n",
    "            dfs(i+1, cnt)\n",
    "            for idx,m in enumerate(matrix[i]):\n",
    "                if m:\n",
    "                    idxCounter[idx] += 1\n",
    "            dfs(i+1, cnt+1)\n",
    "            for idx,m in enumerate(matrix[i]):\n",
    "                if m:\n",
    "                    idxCounter[idx] -= 1\n",
    "                    if idxCounter[idx] == 0:\n",
    "                        del idxCounter[idx]\n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        path = [0] * len(matrix[0])\n",
    "\n",
    "        def dfs(i, c):\n",
    "            nonlocal ans, numSelect\n",
    "\n",
    "            if i == len(matrix[0]):\n",
    "                if c != numSelect: return\n",
    "                cover = 0\n",
    "                for j in range(len(matrix)):\n",
    "                    flag = 1\n",
    "                    for k in range(len(matrix[j])):\n",
    "                        if matrix[j][k] == 1 and path[k] == 0:\n",
    "                            flag = 0\n",
    "                            break\n",
    "                    cover += flag\n",
    "                ans = max(ans, cover)\n",
    "                return\n",
    "                \n",
    "            dfs(i+1, c)\n",
    "            path[i] = 1\n",
    "            dfs(i+1, c+1)\n",
    "            path[i] = 0\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        a=[[] for _ in range(n)]\n",
    "        b=[0]*m\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j]==1:\n",
    "                    a[j].append(i)\n",
    "                    b[i]+=1\n",
    "        print(a)\n",
    "        print(b)\n",
    "\n",
    "        ret=0\n",
    "        colsSelect=0\n",
    "        def dfs(i):\n",
    "            nonlocal colsSelect,ret\n",
    "            if i==n or colsSelect==numSelect:\n",
    "                ret=max(ret,b.count(0))\n",
    "                return\n",
    "            rows=a[i]\n",
    "            for j in rows:\n",
    "                b[j]-=1\n",
    "            colsSelect+=1\n",
    "            dfs(i+1)\n",
    "            for j in rows:\n",
    "                b[j]+=1\n",
    "            colsSelect-=1\n",
    "            dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        res = 0\n",
    "        path = []\n",
    "\n",
    "        def get_rows():\n",
    "            count = 0\n",
    "            for r in matrix:\n",
    "                f = True\n",
    "                for i, v in enumerate(r):\n",
    "                    if v == 1 and i not in path:\n",
    "                        f = False\n",
    "                        break\n",
    "                if f:\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if len(path) == numSelect:\n",
    "                res = max(res, get_rows())\n",
    "                return\n",
    "            if i > len(matrix[0]):\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            path.append(i)\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        path = []  # 存放被选择的列的编号\n",
    "        res = 0  # 被覆盖的行数\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            # 递归出口\n",
    "            if i == n:\n",
    "                # 判断选择的列数是否满足要求\n",
    "                if len(path) == numSelect:\n",
    "                    rows = 0\n",
    "                    for i in range(m):\n",
    "                        s = sum(matrix[i][j] for j in path)\n",
    "                        if sum(matrix[i]) == s:\n",
    "                            rows += 1\n",
    "                    res = max(res, rows)\n",
    "                return\n",
    "            \n",
    "            dfs(i + 1)  # 不选 i 列\n",
    "\n",
    "            path.append(i)  # 选择 i 列\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        a=[[] for _ in range(n)]\n",
    "        b=[0]*m\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j]==1:\n",
    "                    a[j].append(i)\n",
    "                    b[i]+=1\n",
    "        ret=0\n",
    "        colsSelect=0\n",
    "        def dfs(i):\n",
    "            nonlocal colsSelect,ret\n",
    "            if i==n or colsSelect==numSelect:\n",
    "                ret=max(ret,b.count(0))\n",
    "                return\n",
    "            rows=a[i]\n",
    "            for j in rows:\n",
    "                b[j]-=1\n",
    "            colsSelect+=1\n",
    "            dfs(i+1)\n",
    "            for j in rows:\n",
    "                b[j]+=1\n",
    "            colsSelect-=1\n",
    "            dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        path = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        sum_row = []\n",
    "        for i in range(m):\n",
    "            sum_row.append(sum(matrix[i]))\n",
    "\n",
    "        def sum_matrix(sub_matrix):\n",
    "            temp = 0\n",
    "            for i in range(m): \n",
    "                s = 0\n",
    "                for k in range(len(sub_matrix)): # k->子矩阵的列数\n",
    "                    s += sub_matrix[k][i]\n",
    "                if s == sum_row[i]:\n",
    "                    temp += 1\n",
    "            return temp\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            nonlocal numSelect\n",
    "            if numSelect == 0: # 全部选完\n",
    "                ans = max(ans, sum_matrix(path))\n",
    "                return\n",
    "            else:\n",
    "                if i == n:\n",
    "                    return\n",
    "            dfs(i + 1)\n",
    "            path.append([matrix[x][i] for x in range(m)])\n",
    "            numSelect -= 1\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "            numSelect += 1\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        res=0\n",
    "        path=[]\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i==n:\n",
    "                final_path=path.copy()\n",
    "                row=0\n",
    "                if len(final_path)==numSelect:\n",
    "                    for x in range(m):\n",
    "                        s=0\n",
    "                        for j in final_path:\n",
    "                            s +=matrix[x][j]\n",
    "                        if sum(matrix[x])==s:\n",
    "                            row +=1\n",
    "                    res = max(res,row)\n",
    "                return \n",
    "            dfs(i+1)\n",
    "\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "\n",
    "        n = len(matrix[0])\n",
    "        select_cols = set()\n",
    "\n",
    "        def helper(select_cols):\n",
    "            # print(select_cols)\n",
    "            res = 0\n",
    "\n",
    "            for i in range(len(matrix)):\n",
    "                flag = False\n",
    "                for j in range(len(matrix[0])):\n",
    "                    if matrix[i][j] == 1 and j not in select_cols:\n",
    "                        flag = True \n",
    "                        break \n",
    "                if not flag:\n",
    "                    res += 1\n",
    "            return res \n",
    "\n",
    "\n",
    "        \n",
    "        def dfs(i, sn, ans):\n",
    "            if i == n:\n",
    "                ans[0] = max(ans[0], helper(select_cols))\n",
    "                return \n",
    "\n",
    "\n",
    "            dfs(i+1, sn, ans)\n",
    "            \n",
    "            # print(select_cols, sn, i, n)\n",
    "            if sn > 0:\n",
    "                select_cols.add(i)\n",
    "                dfs(i+1, sn-1, ans)\n",
    "                select_cols.remove(i)\n",
    "\n",
    "        ans = [0]\n",
    "        dfs(0, numSelect, ans)\n",
    "\n",
    "        return ans[0]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        path = set(range(m))\n",
    "        cols = defaultdict(set)\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, num in enumerate(row):\n",
    "                if(num == 1):\n",
    "                    cols[j].add(i)\n",
    "        def dfs(i):\n",
    "            nonlocal numSelect, ans\n",
    "            if(i == n):\n",
    "                ans = max(ans, len(path))\n",
    "                return \n",
    "            if(numSelect > 0):\n",
    "                numSelect-=1\n",
    "                dfs(i+1)\n",
    "                numSelect+=1\n",
    "            rmv = []\n",
    "            for row in cols[i]:\n",
    "                if row in path:\n",
    "                    path.remove(row)\n",
    "                    rmv.append(row)\n",
    "            dfs(i+1)\n",
    "            for item in rmv:\n",
    "                path.add(item)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        def isCover(row, path):\n",
    "            for r, c in zip(row, path):\n",
    "                if r==1 and c==0:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        def maxCover(path):\n",
    "            ans = 0\n",
    "            for row in matrix:\n",
    "                ans += isCover(row, path)\n",
    "            return ans\n",
    "        \n",
    "        # 方法一：从答案的角度\n",
    "        # def dfs(i, numSelect):\n",
    "        #     if numSelect==0:\n",
    "        #         m = maxCover(path)\n",
    "        #         nonlocal res\n",
    "        #         res = max(res, m)\n",
    "        #         return\n",
    "\n",
    "        #     for j in range(i, cols):\n",
    "        #         path[j] = 1\n",
    "        #         dfs(j+1, numSelect-1)\n",
    "        #         path[j] = 0\n",
    "        \n",
    "        # cols = len(matrix[0])  \n",
    "        # path = [0] * cols\n",
    "        # res = 0\n",
    "        # dfs(0, numSelect)\n",
    "        # return res\n",
    "        # 方法二：从输入的角度\n",
    "        def dfs(i):\n",
    "            if i == cols:\n",
    "                if sum(path)==numSelect:\n",
    "                    m = maxCover(path)\n",
    "                    nonlocal res\n",
    "                    res = max(res, m)\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "            # 选\n",
    "            path[i] = 1\n",
    "            dfs(i+1)\n",
    "            path[i] = 0\n",
    "\n",
    "\n",
    "        cols = len(matrix[0])  \n",
    "        path = [0] * cols\n",
    "        res = 0\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans=0\n",
    "        m=len(matrix)\n",
    "\n",
    "        n=len(matrix[0])\n",
    "        \n",
    "        path=[]\n",
    "\n",
    "        def dfs(i):\n",
    "            \n",
    "            nonlocal ans\n",
    "            if i==n:\n",
    "                final_path=path.copy()\n",
    "                row=0\n",
    "                if len(final_path)==numSelect:\n",
    "\n",
    "                    for c in range(m):\n",
    "                        s=0\n",
    "                        for j in final_path:\n",
    "                            s+=matrix[c][j]\n",
    "                        if sum(matrix[c])==s:\n",
    "                            row+=1\n",
    "                    ans=max(ans,row)\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        # 选完列是边界, 边界考察各行中没选中的列是否有1, 无则覆盖有则不覆盖\n",
    "        path, self.ans = [], 0\n",
    "        def dfs(i,j):\n",
    "            if self.ans == len(matrix):\n",
    "                return\n",
    "            if i == 0: # 选完了列\n",
    "                count = len(matrix) # 假设所有都覆盖\n",
    "                for row in matrix:\n",
    "                    for col in range(len(matrix[0])):\n",
    "                        if col in path: # 被选中的列\n",
    "                            continue\n",
    "                        if row[col]: # 此行是否有1\n",
    "                            count -= 1 # 减去不被覆盖的行\n",
    "                            if count < self.ans:\n",
    "                                return\n",
    "                            break\n",
    "                self.ans = max(count, self.ans)\n",
    "                return\n",
    "            if j == len(matrix[0]): # 未选满列\n",
    "                return\n",
    "            path.append(j)\n",
    "            dfs(i-1, j+1) # 这一列选了\n",
    "            path.pop(-1)\n",
    "            dfs(i, j+1) # 这一列没选\n",
    "        dfs(numSelect, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        if m <= numSelect:\n",
    "            return n\n",
    "        def dfs(i):\n",
    "            if len(path) == numSelect:\n",
    "                demo = path.copy()\n",
    "                cout = 0\n",
    "                for row in matrix:\n",
    "                    if all([col==0 for subscript, col in enumerate(row) if subscript not in demo]):\n",
    "                        cout += 1\n",
    "                    # for subscript, col in enumerate(row):\n",
    "                    #     if subscript in demo: continue\n",
    "                    #     if col == 1:\n",
    "                    #         cout -= 1\n",
    "                    #         break\n",
    "                ans.append(cout)\n",
    "                return\n",
    "            for j in range(i, m):\n",
    "                path.append(j)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        import itertools as it\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        nums = [i for i in range(n)]\n",
    "        colList = list(it.combinations(nums,numSelect))\n",
    "        rowdict = dict()\n",
    "        for i in range(m):\n",
    "            tset = set()\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    tset.add(j)\n",
    "            rowdict[i] = tset\n",
    "        ans = 0\n",
    "        for li in colList:\n",
    "            t = set(li)\n",
    "            cnt = 0\n",
    "            for r in rowdict:\n",
    "                trow = rowdict[r]\n",
    "                if t|trow == t:\n",
    "                    cnt += 1\n",
    "            ans = max(ans,cnt)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        path = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        sum_row = []\n",
    "        for i in range(m):\n",
    "            sum_row.append(sum(matrix[i]))\n",
    "\n",
    "        def sum_matrix(sub_matrix):\n",
    "            temp = 0\n",
    "            print(sub_matrix)\n",
    "            for i in range(m): \n",
    "                s = 0\n",
    "                for k in range(len(sub_matrix)): # k->子矩阵的列数\n",
    "                    s += sub_matrix[k][i]\n",
    "                if s == sum_row[i]:\n",
    "                    temp += 1\n",
    "            print(temp)\n",
    "            return temp\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            nonlocal numSelect\n",
    "            # print(path)\n",
    "            if numSelect == 0: # 全部选完\n",
    "                ans = max(ans, sum_matrix(path))\n",
    "                return\n",
    "            else:\n",
    "                if i == n:\n",
    "                    return\n",
    "            dfs(i + 1)\n",
    "            path.append([matrix[x][i] for x in range(m)])\n",
    "            numSelect -= 1\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "            numSelect += 1\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:\n",
    "        ans = 0\n",
    "        waiting = []\n",
    "\n",
    "        def count(matrix, cols):\n",
    "            cnt = 0\n",
    "            for row in matrix:\n",
    "                if all(x == 0 for x in row):\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    flag = True\n",
    "                    for i in range(len(row)):\n",
    "                        if row[i] == 1 and i not in cols:\n",
    "                            flag = False\n",
    "                    if flag:\n",
    "                        cnt += 1\n",
    "                            \n",
    "            return cnt\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i > len(matrix[0]):\n",
    "                return\n",
    "            if len(waiting) == numSelect:\n",
    "                cnt = count(matrix, waiting)\n",
    "                print(waiting, cnt)\n",
    "                ans = max(ans, cnt)\n",
    "                print(ans)\n",
    "                return \n",
    "            \n",
    "            # not choose ith column\n",
    "            dfs(i+1)\n",
    "\n",
    "            # choose ith column\n",
    "            waiting.append(i)\n",
    "            dfs(i+1)\n",
    "            waiting.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
